package algorithm.middle;

import com.sun.xml.internal.ws.client.sei.ResponseBuilder;
import pojo.ListNode;
import sun.swing.table.DefaultTableCellHeaderRenderer;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: algorithm.middle
 * @Author: 江岸
 * @CreateTime: 2021-06-01 20:15
 * @Description:
 */
public class SortList148 {


    //找到链表中点进行分隔
    public ListNode sortList(ListNode head){
        if (head==null || head.next==null) return head;
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode B = slow.next;
        slow.next = null;
        ListNode h1 = sortList(head);
        ListNode h2 = sortList(B);
        return merge(h1,h2);
    }

    //合并两个有序链表
    public ListNode merge(ListNode A,ListNode B){
        if (A==null) return B;
        if (B==null) return A;
        if (A.val<B.val){
            A.next = merge(A.next,B);
            return A;
        }else {
            B.next = merge(A,B.next);
            return B;
        }
    }
}
